//
//  DataOperate.m
//  lianliankan
//
//

#import "DataOperate.h"

@implementation DataOperate

// 定义各方向在行和列上的位移
static int targetinfo[4][2] = {
	{-1, 0},	// up
	{0, 1},		// right
	{1, 0},		// down
	{0, -1}		// left
};

/**
 * 生成连连看数据
 * @param int rows 行数
 * @param int cols 列数
 * @param int type 连连看中图片的种类
 * @return NSMutableArray* data 返回连连看数据
 */
+ (NSMutableArray *) generateGameData: (id)sender rowsnum: (int)rows colsnum: (int)cols datatype: (int)type
{
	// 包含所有图片的数组
    NSMutableArray *totaldata = [[[NSMutableArray alloc] init] autorelease];
	// 连连看按行列排列的数组
	NSMutableArray *data = [[[NSMutableArray alloc] init] autorelease];
	int temp;
	
	// 如果设定行或者列为空返回空数组
    if ( 0 == rows || 0 == cols) {
        return data;
    }
    
	// 图片总数
    int total = (int) rows * cols;
    
	// 加入图片时一次加入两张
    for (int i = 0; i < total/2; i += 1) 
	{
		if (i < type) {
			temp = i;
		}
		else
		{
			// 取0-1随机数×图片种类
			temp = (int) (arc4random() % 100) * type / 100;
		}
		// 转化为字符串类型
		NSString *tempstring = [NSString stringWithFormat: @"%d", temp];
        // 加入数据
		[totaldata addObject: tempstring];
        [totaldata addObject: tempstring];
    }
	
	// 数组随机排序
	for (int j = 0, jLen = [totaldata count]; j < jLen; j++) 
	{
		// 取随机位置与当前位置元素对调
		int tempIndex = (NSInteger) arc4random() % (jLen/2) + jLen/2;
		[totaldata exchangeObjectAtIndex: (NSInteger)j withObjectAtIndex: tempIndex];
	}
    
	// 将数据按行列写入到数组中
	for (int row = 0; row < rows + 2; row++) 
	{
		// 临时数组
		NSMutableArray *temp = [[[NSMutableArray alloc] init] autorelease];
		for (int col = 0; col < cols + 2; col++) 
		{
			// 第一行、最后一行、第一列、最后一列为预留空余位，标记为-1
			if (0 == row || (rows + 1 == row) || 0 == col || (cols + 1 == col)) 
			{
				[temp addObject: [NSString stringWithFormat:@"%d", kEmpty]];
			}
			else
			{
				[temp addObject: [totaldata objectAtIndex: (NSInteger)(row - 1)*cols + col - 1]];
			}
		}
		// 将临时数组加入到总的数组中
		[data addObject:temp];
	}
    
    return data;
}

/**
 *　刷新当前数据
 * @param NSMutableArray* data 当前连连看数据
 * @return NSMutableArray* data
 */
+ (NSMutableArray *) refreshGameData: (id)sender gameData: (NSMutableArray *)data
{
	// 有效的数据
	NSMutableArray *valid = [[[NSMutableArray alloc] init] autorelease];
	// 获取当前所有有效数据（不为-1）
	for (int row = 0; row < [data count]; row++) 
	{
		NSMutableArray *datarow = [data objectAtIndex: row];
		for (int col = 0; col < [datarow count]; col++) 
		{
			if (![[datarow objectAtIndex: col] isEqualToString: [NSString stringWithFormat: @"%d", kEmpty]]) {				
				[valid addObject: [datarow objectAtIndex: col]];
			}
		}
	}
	
	// 将有效数据随即排序
	for (int i = 0, iLen = [valid count]; i < iLen; i++) 
	{
		NSInteger tempIndex = (NSInteger) rand() % iLen;
		[valid exchangeObjectAtIndex: (NSInteger)i withObjectAtIndex: tempIndex];
	}
	
	int pos = 0;
	// 按照之前有效数据的位置将新随即的数据重新排列插入
	for (int row = 0; row < [data count]; row++) 
	{
		NSMutableArray *datarow = [data objectAtIndex: row];
		for (int col = 0; col < [datarow count]; col++) 
		{
			if (![[datarow objectAtIndex: col] isEqualToString: [NSString stringWithFormat: @"%d", kEmpty]]) {				
				[datarow replaceObjectAtIndex: (NSInteger)col withObject:[ valid objectAtIndex: (NSInteger)pos++]];
			}
		}
	}
	
	return data;
}

/**
 * 查找任意两个匹配的节点路径，如果没有可行的路径，返回一个空数组
 * @param NSMutableArray *movableSprites 图片节点
 * @param NSMutableArray *data 连连看数据
 * @return NSMutableArray *path　路径信息
 *
 */
+ (NSMutableArray *) fetchRandomMatchPath : (id) sender gameData : (NSMutableArray *) data
{
	// 将要返回的路径
	NSMutableArray *path = [[[NSMutableArray alloc] init] autorelease];
	
	// 可行的路径
	NSMutableDictionary *feasibleNodes = [NSMutableDictionary dictionary]; 
	
	for (NSMutableArray *rowSprites in data) 
	{
		for (ImageNode *sprite in rowSprites) 
		{
			if (![sprite isEqual: [NSNull null]]) 
			{
				NSString *key = [NSString stringWithFormat:@"%d", [sprite imageType]];
				NSMutableArray *temp = [NSMutableArray array];
				
				if ([feasibleNodes objectForKey:key]) 
				{
					temp = [feasibleNodes objectForKey:key];
				}
				[temp addObject:sprite];
				
				[feasibleNodes setObject:temp forKey:key];
			}
		}
	}
	
	NSArray *keys = [feasibleNodes allKeys];
	for (NSString *key in keys) 
	{
		NSMutableArray *values = [feasibleNodes objectForKey:key];
		// 有成对出现的图片节点才进行比较（数组大于1）
		NSUInteger arrayLen = [values count];
		for (int i = 0; i < arrayLen; i++)
		{
			for (int j = i + 1; j < arrayLen; j ++) 
			{
				ImageNode *beginNode = (ImageNode *)[values objectAtIndex:i];
				ImageNode *endNode = (ImageNode *)[values objectAtIndex:j];
                
				int begin[2] = {[beginNode row],[beginNode col]};
				int end[2] = {[endNode row],[endNode col]};
				
				path = [self fetchPathBetweenTwoPoint:self beginPosition:begin endPosition:end gameData:data];
                
				if ([path count])
				{
					return path;
				}
			}
		}
	}
	
	return path;
}

// 根据行与列找到对应的节点
+ (ImageNode *) fetchImageNode : (NSMutableArray *) data row : (NSInteger) row col : (NSInteger) col
{
	ImageNode *node = [[ImageNode alloc] init];
	
	for (ImageNode *sprite in data) 
	{
		if ([sprite row] == row && [sprite col] == col) 
		{
			node = sprite;
		}
	}
	
	return node;
}

/**
 * 获取两点间的路径
 * @param int* begin 开始位置
 * @param int* end 结束位置
 * @param NSMutableArray* data 连连看数据
 * @return NSMutableArray* 返回两点间路径
 */
+ (NSMutableArray *) fetchPathBetweenTwoPoint: (id)sender beginPosition: (int *)begin endPosition: (int *)end gameData: (NSMutableArray *)data
{
    NSMutableArray *path = [[[NSMutableArray alloc] init] autorelease];
	
	int beginTargets[kTargetNum], endTargets[kTargetNum];
	int targetBegin,targetEnd;
	
	//　获取开始和结束点各方向的可行性
	for (int i =0; i < kTargetNum; i++) 
	{
		
		beginTargets[i] = [[[data objectAtIndex:(NSInteger)(begin[0] + targetinfo[i][0])] objectAtIndex:(NSInteger)(begin[1] + targetinfo[i][1])] isEqual:[NSNull null]]? 1 : 0;
		endTargets[i] = [[[data objectAtIndex:(NSInteger)(end[0] + targetinfo[i][0])] objectAtIndex:(NSInteger)(end[1] + targetinfo[i][1])] isEqual:[NSNull null]]? 1 : 0;
		
		//如果是相邻位置的，存入路径，返回
		if ((begin[0] + targetinfo[i][0] == end[0]) && (begin[1] + targetinfo[i][1] == end[1])) 
		{
			[path addObject:[NSString stringWithFormat:@"%d,%d", begin[0], begin[1]]];
			[path addObject:[NSString stringWithFormat:@"%d,%d", end[0], end[1]]];
			return path;
		}
	}
    
	// 同行或同列（方式１）
	if (begin[0] == end[0] || begin[1] == end[1]) 
	{
		// 如果同行
		if (begin[0] == end[0]) 
		{
			targetBegin = begin[1] < end[1] ? kTargetRight : kTargetLeft;
		}
		// 如果同列
		else
		{
			targetBegin = begin[0] < end[0] ? kTargetDown : kTargetUp;
		}
		
		// 如果开始和结束点的方向可行
		if (beginTargets[targetBegin] && endTargets[(targetBegin+2)%kTargetNum]) 
		{
			path = [self fetchPathPartenOne:self beginPosition:begin endPosition:end gameData:data findTarget:targetBegin];
			if ([path count]) 
			{
				return path;
			}
		}
		
		
		for (int t = 0; t < kTargetNum; t++) 
		{
			// 匹配U型（方式２）
			if (beginTargets[t] && endTargets[t] && t != targetBegin && t != (targetBegin+2)%2) 
			{
				path = [self fetchPathPartenTwo:self beginPosition:begin endPosition:end gameData:data findTarget:t];
				if ([path count])
				{
					return path;
				}
			}
		}
		
	}
	else
	{
		// 匹配L型（方式３）
		targetBegin = begin[0] < end[0] ? kTargetDown : kTargetUp;
		targetEnd = begin[1] < end[1] ? kTargetLeft : kTargetRight;
		if (beginTargets[targetBegin] && endTargets[targetEnd]) {
			path = [self fetchPathPartenThree:self beginPosition:begin endPosition:end gameData:data findTarget:targetBegin];
			if ([path count])
			{
				return path;
			}
		}
		
		// 匹配L型（方式３）
		targetBegin = begin[1] < end[1] ? kTargetRight : kTargetLeft;
		targetEnd = begin[0] < end[0] ? kTargetUp : kTargetDown;
		if (beginTargets[targetBegin] && endTargets[targetEnd]) {
			path = [self fetchPathPartenThree:self beginPosition:begin endPosition:end gameData:data findTarget:targetBegin];
			if ([path count])
			{
				return path;
			}
		}
		
		// 匹配Z型（方式４）
		targetBegin = begin[0] < end[0] ? kTargetDown : kTargetUp;
		targetEnd = (targetBegin + 2) % kTargetNum;
		if (beginTargets[targetBegin] && endTargets[targetEnd]) {
			path = [self fetchPathPartenFour:self beginPosition:begin endPosition:end gameData:data findTarget:targetBegin];
			if ([path count])
			{
				return path;
			}
		}
		
		// 匹配Z型（方式４）
		targetBegin = begin[1] < end[1] ? kTargetRight : kTargetLeft;
		targetEnd = (targetBegin + 2) % kTargetNum;
		if (beginTargets[targetBegin] && endTargets[targetEnd]) {
			path = [self fetchPathPartenFour:self beginPosition:begin endPosition:end gameData:data findTarget:targetBegin];
			if ([path count])
			{
				return path;
			}
		}
		
		
		for (int t = 0; t < kTargetNum; t++) 
		{
			// 匹配U型（方式２）
			if (beginTargets[t] && endTargets[t]) 
			{
				path = [self fetchPathPartenTwo:self beginPosition:begin endPosition:end gameData:data findTarget:t];
				if ([path count])
				{
					return path;
				}
			}
		}
	}
	
    return path;
}

/**
 * 获取两点间的路径（方式1）
 * 两点在同一行或者同一列，只判断本行或者本列
 * @param int* begin 开始位置
 * @param int* end 结束位置
 * @param NSMutableArray* data 连连看数据
 * @return NSMutableArray* 返回两点间路径
 */
+ (NSMutableArray *) fetchPathPartenOne: (id)sender beginPosition: (int *)begin endPosition: (int *)end gameData: (NSMutableArray *)data findTarget: (int)target
{	
    NSMutableArray *path = [[[NSMutableArray alloc] init] autorelease];
	int row = begin[0];
	int col = begin[1];
	
	while (YES) 
	{
		if (![self addItemToPath:self currentRow: row currentCol: col beginPosition: begin endPosition: end gameData: data currentPath: path]) 
		{
			return [[[NSMutableArray alloc] init] autorelease];
		}
		
		// 如果是结尾，跳出
		if (row == end[0] && col == end[1]) 
		{
			break;
		}
		
		//　转到下个节点
		row += targetinfo[target][0];
		col += targetinfo[target][1];
	}
    
    return path;
}

/**
 * 获取两点间的路径（方式２）
 * U字形路径
 * @param int* begin 开始位置
 * @param int* end 结束位置
 * @param NSMutableArray* data 连连看数据
 * @return NSMutableArray* 返回两点间路径
 */
+ (NSMutableArray *) fetchPathPartenTwo: (id)sender beginPosition: (int *)begin endPosition: (int *)end gameData: (NSMutableArray *)data findTarget: (int)target
{	
    NSMutableArray *path = [[[NSMutableArray alloc] init] autorelease];
	int row, col;
	int turnOne[2], turnTwo[2];
	// 记录初始方向
	int targetBegin = target;
	
	// 根据方向的不同，确定转折点的坐标
	if (target == kTargetUp || target == kTargetDown) 
	{
		turnOne[0] = turnTwo[0] = target == kTargetUp ? (MIN(begin[0], end[0]) - 1) : (MAX(begin[0], end[0]) + 1);
		turnOne[1] = begin[1];
		turnTwo[1] = end[1];
	}
	else
	{
		turnOne[0] = begin[0];
		turnTwo[0] = end[0];
		turnOne[1] = turnTwo[1] = target == kTargetLeft ? (MIN(begin[1], end[1]) - 1) : (MAX(begin[1], end[1]) + 1);
	}
	
	while (YES) 
	{
		// 初始状态
		row = begin[0];
		col = begin[1];
		target = targetBegin;
		path = [[[NSMutableArray alloc] init] autorelease];
		
		while (YES) 
		{
			// 如果此路径已被占用，跳出尝试下一种路径
			if (![self addItemToPath:self currentRow: row currentCol: col beginPosition: begin endPosition: end gameData: data currentPath: path]) 
			{
				break;
			}
			
			// 如果是结尾，返回路径
			if (row == end[0] && col == end[1]) 
			{
				return path;
			}
			
			// 第一个转折点
			if (row == turnOne[0] && col == turnOne[1]) 
			{
				//　转折后的运行方向
				if (targetBegin == kTargetUp || targetBegin == kTargetDown) 
				{
					target = begin[1] < end[1] ? kTargetRight : kTargetLeft;
				}
				else
				{
					target = begin[0] < end[0] ? kTargetDown : kTargetUp;
				}
			}
			
			// 第二个转折点
			if (row == turnTwo[0] && col == turnTwo[1]) 
			{
				target = (targetBegin + 2) % kTargetNum;
			}
			
			// 下一个点
			row += targetinfo[target][0];
			col += targetinfo[target][1];
		}
		
		// 更新转折点的位置
		turnOne[0] += targetinfo[targetBegin][0];
		turnOne[1] += targetinfo[targetBegin][1];
		turnTwo[0] += targetinfo[targetBegin][0];
		turnTwo[1] += targetinfo[targetBegin][1];
		
		// 如果转折点越界，跳出循环
		if (turnOne[0] < 0 || turnOne[1] < 0 || turnOne[0] >= [data count] || turnOne[1] >= [[data objectAtIndex:0] count]) {
			break;
		}
	}
    
	// 如果未找到路径，返回空数组
    return [[[NSMutableArray alloc] init] autorelease];
}

/**
 * 获取两点间的路径（方式３）
 * L字形路径
 * @param int* begin 开始位置
 * @param int* end 结束位置
 * @param NSMutableArray* data 连连看数据
 * @return NSMutableArray* 返回两点间路径
 */
+ (NSMutableArray *) fetchPathPartenThree: (id)sender beginPosition: (int *)begin endPosition: (int *)end gameData: (NSMutableArray *)data findTarget: (int)target
{	
    NSMutableArray *path = [[[NSMutableArray alloc] init] autorelease];
	int row = begin[0];
	int col = begin[1];
	
	while (YES) 
	{
		if (![self addItemToPath:self currentRow: row currentCol: col beginPosition: begin endPosition: end gameData: data currentPath: path]) 
		{
			return [[[NSMutableArray alloc] init] autorelease];
		}
		
		// 如果是结尾，跳出
		if (row == end[0] && col == end[1]) 
		{
			break;
		}
		
		// 如果是拐点，由纵向改为横向
		if (row == end[0]) 
		{
			target = col < end[1] ? kTargetRight : kTargetLeft;
		}
		
		// 如果是拐点，由横向改为纵向
		if (col == end[1]) 
		{
			target = row < end[0] ? kTargetDown : kTargetUp;
		}
		
		row += targetinfo[target][0];
		col += targetinfo[target][1];
	}
    
    return path;
}

/**
 * 获取两点间的路径（方式４）
 * Z字形路径
 * @param int* begin 开始位置
 * @param int* end 结束位置
 * @param NSMutableArray* data 连连看数据
 * @return NSMutableArray* 返回两点间路径
 */
+ (NSMutableArray *) fetchPathPartenFour: (id)sender beginPosition: (int *)begin endPosition: (int *)end gameData: (NSMutableArray *)data findTarget: (int)target
{	
    NSMutableArray *path = [[[NSMutableArray alloc] init] autorelease];
    int row, col;
	int turnOne[2], turnTwo[2];
	int targetBegin = target;
	
	// 根据方向的不同，确定转折点的位置
	if (target == kTargetUp || target == kTargetDown) 
	{
		turnOne[0] = turnTwo[0] = begin[0] + targetinfo[targetBegin][0];
		turnOne[1] = begin[1];
		turnTwo[1] = end[1];
	}
	else
	{
		turnOne[0] = begin[0];
		turnTwo[0] = end[0];
		turnOne[1] = turnTwo[1] = begin[1] + targetinfo[targetBegin][1];
	}
	
	while (YES) 
	{
		// 如果转折点与终点同行或同列
		if (turnOne[0] == end[0] || turnOne[1] == end[1]) {
			break;
		}
		
		// 初始状态
		row = begin[0];
		col = begin[1];
		target = targetBegin;
		path = [[[NSMutableArray alloc] init] autorelease];
		
		while (YES) 
		{
			// 如果此路径已被占用，跳出尝试下一种路径
			if (![self addItemToPath:self currentRow: row currentCol: col beginPosition: begin endPosition: end gameData: data currentPath: path]) 
			{
				break;
			}
			
			// 如果是结尾，跳出
			if (row == end[0] && col == end[1]) 
			{
				return path;
			}
			
			// 第一个转折点
			if (row == turnOne[0] && col == turnOne[1]) 
			{
				//　更新转折后的方向
				if (targetBegin == kTargetUp || targetBegin == kTargetDown) 
				{
					target = begin[1] < end[1] ? kTargetRight : kTargetLeft;
				}
				else
				{
					target = begin[0] < end[0] ? kTargetDown : kTargetUp;
				}
			}
			
			// 第二个转折点
			if (row == turnTwo[0] && col == turnTwo[1]) 
			{
				target = targetBegin;
			}
			
			row += targetinfo[target][0];
			col += targetinfo[target][1];
		}
		
		// 更新转折点的位置
		turnOne[0] += targetinfo[targetBegin][0];
		turnOne[1] += targetinfo[targetBegin][1];
		turnTwo[0] += targetinfo[targetBegin][0];
		turnTwo[1] += targetinfo[targetBegin][1];
	}
    
    return [[[NSMutableArray alloc] init] autorelease];
}


/**
 * 向路径中添加节点
 * @param int row 当前行
 * @param int col 当前列
 * @param int* begin 开始位置
 * @param int* end 结束位置
 * @param NSMutableArray* data 连连看数据
 * @param NSMutableArray* path 当前路径
 * @return boolean　是否添加成功
 */
+ (Boolean) addItemToPath: (id)sender currentRow: (int)row currentCol: (int)col beginPosition: (int *)begin endPosition: (int *)end gameData: (NSMutableArray *)data currentPath : (NSMutableArray *)path
{
	// 如果越界，返回
	if (row < 0 || col < 0 || (row >= [data count]) || (col >= [[data objectAtIndex:0] count])) {
		return NO;
	}
	
	// 如果是开始或结束节点
	if ((row == begin[0] && col == begin[1]) || (row == end[0] && col == end[1])) 
	{
		[path addObject:[NSString stringWithFormat:@"%d,%d", row, col]];
	}
	// 如果是路径节点
	else
	{
		// 如果路径节点可行
		if ([[[data objectAtIndex:(NSInteger)row] objectAtIndex:(NSInteger)col] isEqual:[NSNull null]]) 
		{
			[path addObject:[NSString stringWithFormat:@"%d,%d", row, col]];
		}
		else
		{
			return NO;
		}
	}
	
	return YES;
}

- (void) dealloc
{
    [super dealloc];
}

@end
